#include <iostream>
#include <utility>
#include <assert.h>
#include <stack>

using namespace std;

class BSTreeNode
{
public:
	int value;
	struct BSTreeNode * left;
	struct BSTreeNode * right;
	BSTreeNode(int v) : value(v), left(NULL), right(NULL) {
	}
};

class BSTree
{
	BSTreeNode * root;
public:
	BSTree(): root(NULL) {}

	BSTreeNode * getRoot() {
		return root;
	}
	
	void insert(int key) {
		BSTreeNode * n = new BSTreeNode(key);	
		insert(n);
	}

	void insert(BSTreeNode * node) {
		assert(node);
		if (root == NULL) {
			root = node;
			return;
		}

		BSTreeNode ** cur = &root;
		while(*cur != NULL) {
			if (node->value < (*cur)->value)
				cur = &((*cur)->left);
			else if (node->value > (*cur)->value)
				cur = &((*cur)->right);
			else
				break;
		}

		if(*cur == NULL)
			*cur = node;
	}
	
	static void print(BSTreeNode * root) {
		cout << root->value << " ";

		if (root->left)
			cout <<root->left->value<< " ";
		else
			cout << "NULL" << " ";
		if (root->right)
			cout << root->right->value << " ";
		else
			cout << "NULL" << " ";
		cout << endl;

		if (root->left)
			print(root->left);
		if (root->right)
			print(root->right);
	}
	
	//use loop to iso this tree
	//this function uses a post-order traversal algorithm to visit each node, i.e, exchange left and right pointers of each node, 
	//by referencing the following link:
	//http://www.cnblogs.com/ybwang/archive/2011/10/04/lastOrderTraverse.html
	//this key point is that, we have to store the information "if the right child has been visited" in each node in the stack.

	void iso_loop() {
		if (root == NULL)
			return;

		stack<pair<BSTreeNode *, bool>> st;	//in the stack, we store the pointer to each node, 
							//and if its right child has been visited.

		for(BSTreeNode * cur = root; cur != NULL; cur = cur->left)
			st.push(make_pair(cur, false));
		
		while(!st.empty()) {
			pair<BSTreeNode *, bool> &p = st.top();
			
			if (p.first->right == NULL || p.second) {		//this is a leaf
				cout << "visit " << p.first->value << endl;
				BSTreeNode * temp = p.first->left;
				p.first->left = p.first->right;
				p.first->right = temp;
				st.pop();
			} else {
				p.second = true;
				BSTreeNode * bn = p.first->right;
				while(bn) {
					st.push(make_pair(bn, 0));
					bn = bn->left;
				}
			}
		}
	}

	//use recursion to iso this tree
	void iso_recursive() {
		return iso_recursive_helper(root);
	}

	static void iso_recursive_helper(BSTreeNode * root) {
		if (root == NULL)
			return;

		iso_recursive_helper(root->left);
		iso_recursive_helper(root->right);

		BSTreeNode * temp = root->left;
		root->left = root->right;
		root->right = temp;
	}
};

int main()
{
	BSTree bst;
	for (int i = 0; i < 10; ++i)
		bst.insert(rand()%20);

	cout << "orig:" << endl;
	BSTree::print(bst.getRoot());
	
//	bst.iso_recursive();
	bst.iso_loop();

	cout << "after iso:" << endl;
	BSTree::print(bst.getRoot());
	return 0;
}
